//
// Created by xili on 2024/8/31 9:27.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution {
public:
    unordered_map<long, long> dp;

    int integerReplacement(int n) {
        long t = n;
        if (t == 1) {
            return 0;
        }
        if (dp.count(t)) {
            return dp[t];
        }
        if (n % 2 == 0) {
            dp[t] = integerReplacement(t / 2) + 1;
        } else {
            dp[t] = min(integerReplacement((t + 1) / 2), integerReplacement((t - 1) / 2)) + 2;
        }
        return dp[t];
    }
};